Masala #0929

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 60 %
14

  

Qal'a himoyasi

Berlandiya mamlakatida bir qal'a mavjud. Bu qal'aga dushman hujum qilmoqchi. Siz qal'ani yovuz dushmanlarning hujumidan himoya qilish uchun kamonchi elflarni boshqarishingiz kerak. Qal'a uch tomondan o'tib bo'lmas to'siqlar bilan himoyalangan va qolgan to'rtinchi kirish tomonida esa \(n\) ta bo'limdan iborat devor bor. Ayni paytda \(i\)-bo'limda \(a_i\) ta kamonchi elflar joylashgan. Malumki \(i-\)bo'limda joylashgan har bir kamonchi \(r\) dan ortiq bo'lmagan masofalardagi bo'limga hujim qilayotgan dushmanga qarshi o'q uzaoladi, ya'ni \(j(|i-j|\leq r)\) raqamli bo'limlarga o'q uzaoladi. 

\(i-\)bo'limning xafsizligi - bu qisimga hujum qilayotgan dushmanlarga o'q uzishi mumkin bo'lgan kamonchilarning umumiy soniga teng. Mudofa rejasining ishonchliligi har qanday bo'lim xafsizligining minimal qiymati hisoblanadi.

Dushman hujum qilishiga juda oz vaqt qoldi va siz bo'limlardagi kamonchilarni qayta joylashtirib chiqish uchun vaqingiz yo'q. Biroq sizda bo'limlarga joylashtirish uchun zaxirada \(k\) ta kamonchilar zaxirasi mavjud. Sizning vazifangiz mudofa rejasining ishonchliligini maksimal qilishdan iborat.


Kiruvchi ma'lumotlar:

Dastlabki satrda \(n,r,k(1\leq n\leq 500000, 0\leq r \leq n, 0\leq k\leq 10^{18})\) mos ravshda devorni tashkil etuvchi bo'limlar soni, har bir kamonchi o'q uzishi mumkun bo'lgan maksimal masofa va zaxiradagi kamonchilar soni. Kiyingi satrda \(n\) ta butun son \(a_i(0\leq a_i\leq 10^9)\) \(i-\)bo'limda joylashgan kamonchilar soni.


Chiquvchi ma'lumotlar:

Yagona butun sonni chop eting - mudofa rejasi ishonchliligining maksimal mumkun bo'lgan qiymati, ya'ni zaxiradagi \(k\) ta kamonchilarni optimal joylashtirish orqali devorning bir qismini himoya qilishning maksimal mumkun bo'lgan minimal qiymatini chop eting.


Misollar
# input.txt output.txt
1
4 1 2
5 1 1 2
5
2
5 0 6
5 4 3 4 9
5
Izoh:

1-test: Jami bo'li \(4\) ta bo'lim devorni himoyalaydi.
\(1-\)bo'limda \(5\) ta kamonchi bor va bu bo'limga \(2-\)bo'limdagi kamonchilar yordam beraoladi, sababi \(|1-2|\leq r\) va bu bo'limning himoyasi \(5+1=6\) ga teng.
\(2-\)bo'limdiki esa \(5+1+1=7\) ga teng.
\(3-\)bo'limniki esa \(1+1+2=4\) ga teng.
\(4-\)bo'limniki \(1+2=3\) ga teng.
Siz agar uchunchi bo'limga zaxiradagi \(2\) ta kamonchini joyllashtirsangiz ikkinchi bo'liming himoyasi \(9\) ga, uchunchi bo'limning himoyasi \(6\) ga va to'rtinchi bo'limning himoyasi \(5\) ga o'zgaradi. Shunday qilib bo'limlar himoyalarini maksimal qilganimizdan so'ng, barcha bo'limlar uchun minimal himoyani tanlaymiz. \(min(6, 9, 6, 5) = 5\) bu qal'a devornig himoyasini ifodalaydi.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin